Space cost analysis

Suppose we want to draw a unary-binary tree T of height h having N nodes5. According to our internal representation, for each subtree in the stack we need

  1. one box register to store the box of the TEXtree.
  2. one token register to store the type of the root of the subtree.
  3. 2h′ + 6 dimension registers to store the additional information, where h′ is the height of the subtree.
  4. three counter registers to store the register numbers of the box register, the token register, and the first dimension register above.

The following lemma relates to h and N the number of subtrees of T which are on the stack simultaneously and their heights.

Lemma 7.1  
  1. At any time, there are at most h + 1 subtrees of T on the stack.
  2. For each set $\cal {T}$ of subtrees of T which are on the stack simultaneously we have

    $\displaystyle \sum_{{T^\prime\in {\cal T}}}^{}$(ht(T′) + 1)≤min(N,$\displaystyle {(h+1)(h+2)\over2}$).

Proof  
  1. By induction on h.
  2. The trees in $\cal {T}$ are pairwise disjoint, and each tree of height h′ has at least h′ + 1 nodes. This implies

    $\displaystyle \sum_{{T^\prime\in {\cal T}}}^{}$(ht(T′) + 1)≤N.

    The second part is shown by induction on h. The basis h = 0 is clear. Assume the assumption holds for all trees of height less than h. If $\cal {T}$ contains only subtrees of either the left or the right subtree of T, we have

    $\displaystyle \sum_{{T^\prime\in {\cal T}}}^{}$(ht(T′) + 1)≤$\displaystyle {h(h+1)\over2}$≤$\displaystyle {(h+1)(h+2)\over2}$.

    Otherwise, $\cal {T}$ contains the left or the right subtree Ts of T. Then all elements of $\cal {T}$ - {Ts} belong to the other subtree. This implies
    $\displaystyle \sum_{{T^\prime\in {\cal T}}}^{}$(ht(T′) + 1) ≤ ht(Ts) + 1 + $\displaystyle \sum_{{T^\prime\in {\cal T}-\{T_s\}}}^{}$(ht(T′) + 1)  
      ≤ h + $\displaystyle {h(h+1)\over2}$≤$\displaystyle {(h+1)(h+2)\over2}$.        $\displaystyle \ifmmode$$\displaystyle \Box$$\displaystyle \else$$$\displaystyle \Box$$$\displaystyle \fi$  

Therefore, our implementation uses at most 9h + 2 min(N,(h + 1)(h + 2)/2) registers. In order to compare this with the 10N registers used in the straightforward implementation, an estimation of the average height of a tree with N nodes is needed. Several results, depending on the type of trees and of the randomization model, are cited in Figure [*], which compares the number of registers used in a straightforward implementation with the average number of registers used in our implementation. This table shows clearly the advantage of our implementation.

Figure: The numbers of registers used by a straightforward implementation (second column) and by our modified implementation (third to fifth column) of the RT algorithm are given for different types of trees and randomization models. The formula in parentheses indicates the average height of the respective class of trees, as depending on the number of nodes.
\begin{figure}\vspace{1\baselineskip}\centering \begin{tabular}{\vert c\vert c\v... ...95.37& 143.54\\ \hline \end{tabular}\par \vspace{1\baselineskip}\end{figure}